package com.peng.leetcode.unionFind;

import java.util.*;

/**
 * MinimumHammingDistance
 *
 * 1722. 执行交换操作后的最小汉明距离
 *
 * @author: lupeng6
 * @create: 2021/2/18 10:34
 */
public class MinimumHammingDistance {

    public static void main(String[] args) {
        int[] source = {49,21,79,79,6,67,78,9,91,39,49,32,53,29,97,50,82,55,13,83,63,99,41,6,51,46,31,26,58,18,32,51,44,66,40,35,96,20,35,43,64,96,99,76,11,35,86,96,10,19,70,29,19,47}, target = {33,22,32,71,66,90,78,67,74,76,84,32,25,100,57,7,90,95,33,79,54,99,42,6,32,55,31,14,58,67,48,59,7,50,5,22,11,97,94,14,53,75,3,9,82,74,86,27,21,77,70,29,65,15};
        int[][] allowedSwaps = {{40,41},{41,35},{18,19},{9,51},{48,2},{45,13},{27,45},{16,22},{23,25},{2,6},{5,11},{37,38},{22,48},{13,48},{51,37},{24,19},{2,32},{38,23},{33,34},{37,44},{31,8},{4,26},{34,35},{37,28},{48,34},{27,0},{23,37},{17,29},{38,7},{37,31},{34,42},{26,20},{22,45},{26,29},{40,42},{48,30},{46,49},{12,52},{49,28},{39,14},{23,34},{6,30},{18,12},{52,49},{21,18},{11,4},{2,7},{4,17},{19,27},{33,5},{44,28},{38,9},{34,7},{7,47},{37,13},{51,12},{42,53},{42,21},{18,9},{21,39},{4,33},{29,39},{47,41},{25,13},{50,0},{21,48},{32,27},{33,53},{39,5},{12,25},{52,6},{17,44},{16,52},{0,34},{14,29},{0,19},{13,7},{29,21},{9,22},{28,45},{1,29},{37,17},{38,36},{4,23},{38,21},{35,5},{2,16},{34,30},{37,16},{40,53},{51,47},{20,32},{7,9},{12,15},{26,0},{14,44},{53,11},{48,17}};
        System.out.println(new MinimumHammingDistance().minimumHammingDistance(source, target, allowedSwaps));
    }

    public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        if (source == null || source.length == 0) {
            return 0;
        }

        int size = source.length;
        // 将相同连通分量分组, map
        Map<Integer, List<Integer>> group = new HashMap<>();

        // 并查集
        UnionFind unionFind = new UnionFind(size + 1);
        for (int[] allowedSwap : allowedSwaps) {
            int i = allowedSwap[0];
            int j = allowedSwap[1];
            unionFind.union(i, j);
        }

        for (int i = 0; i < source.length; i++) {
            int root = unionFind.find(i);
            int value = source[i];
            group.putIfAbsent(root, new ArrayList<>());
            group.get(root).add(value);
        }

        // 计算 source 和 target 不相同的
        int answer = 0;

        for (int i = 0; i < target.length; i++) {
            int root = unionFind.find(i);
            int value = target[i];

            List<Integer> integers = group.get(root);

            int index = integers.indexOf(value);
            if (index < 0) {
                answer++;
            } else {
                integers.remove(index);
            }
        }

        return answer;
    }


    static class UnionFind {
        private int[] parent;

        private int[] rank;

        public UnionFind(int size) {
            this.parent = new int[size];
            this.rank = new int[size];
            for (int i = 0; i < size; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public void union(int x, int y) {
            int xRoot = find(x);
            int yRoot = find(y);

            if (xRoot == yRoot) {
                return;
            }
            if (rank[xRoot] >= rank[yRoot]) {
                parent[xRoot] = yRoot;
                rank[yRoot]++;
            } else {
                parent[yRoot] = xRoot;
                rank[xRoot]++;
            }
        }
    }

}
